Caching in general is when some extra data is tracked in local memory to avoid having to recalculate it (if calculation is resource-expensive) or to avoid having to re-fetch it (if the cost of a fetch operation is resource-expensive). A special case of caching involves processors, where cache memory is typically used by the central processing unit of a computing device to reduce the average time to access the main memory. The cache is commonly a smaller, faster memory, which stores copies of the data from the most frequently used main memory locations. As long as most memory accesses are cached memory locations, the average latency of memory accesses tend to be closer to the cache latency rather than to the latency of main memory.
When an application needs data, it first checks whether a copy of that data is in the cache. If so, the application may immediately reads from or writes to the cache, which is significantly faster and less resource-expensive than reading from or writing to a remote data store. Cache is, however, typically smaller in size. Thus, capacity pressures on cache are greater than those on remote data stores. One category of the many approaches for efficient use of cache memory is Least Recently Used (LRU) replacement. Generally, unused or least recently used content in cache is deleted in favor of new data according to LRU replacement approaches. Different management methods may be used for different types of cache. Caches implementing LRU replacement approaches may be referred to as LRU caches.
Standard LRU caches are commonly implemented using a simple doubly-linked list, which drops the least recently used items out of cache when memory pressures exist. This scheme breaks down when the values being cached are combinations of values. For example, a combination of ten values in six segments represents one million potential combinations. Storing even ten thousand of those combinations may require sixty thousand times the size of a single value in storage, with the vast majority of the stored values being repeated thousands of times each.